package leetcode.code1632;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int[] p;

	public int[][] matrixRankTransform(int[][] matrix) {
		int m = matrix.length, n = matrix[0].length;
		int mn = m * n;
		p = new int[mn];
		for (int i = 0; i < mn; i++) {
			p[i] = i;
		}
		List<Map<Integer, Integer>> list = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			list.add(new HashMap<>());
		}
		for (int i = 0; i < m; i++) {
			Map<Integer, Integer> map = new HashMap<>();
			for (int j = 0; j < n; j++) {
				int cur = matrix[i][j];
				int idx = i * n + j;
				union(map.computeIfAbsent(cur, key -> idx), idx);
				union(list.get(j).computeIfAbsent(cur, key -> idx), idx);
			}
		}
		int[] ins = new int[mn];
		List<List<Integer>> nexts = new ArrayList<>();
		for (int i = 0; i < mn; i++) {
			nexts.add(new ArrayList<>());
		}
		for (int i = 0; i < m; i++) {
			Integer[] ids = new Integer[n];
			for (int j = 0; j < n; j++) {
				ids[j] = j;
			}
			int[] nums = matrix[i];
			Arrays.sort(ids, (a, b) -> nums[b] - nums[a]);
			for (int j = 1; j < n; j++) {
				if (nums[ids[j]] != nums[ids[j - 1]]) {
					int a = find(i * n + ids[j]), b = find(i * n + ids[j - 1]);
					nexts.get(a).add(b);
					ins[b]++;
				}
			}
		}

		for (int i = 0; i < n; i++) {
			Integer[] ids = new Integer[m];
			int[] nums = new int[m];
			for (int j = 0; j < m; j++) {
				ids[j] = j;
				nums[j] = matrix[j][i];
			}
			Arrays.sort(ids, (a, b) -> nums[b] - nums[a]);
			for (int j = 1; j < m; j++) {
				if (nums[ids[j]] != nums[ids[j - 1]]) {
					int a = find(ids[j] * n + i), b = find(ids[j - 1] * n + i);
					nexts.get(a).add(b);
					ins[b]++;
				}
			}
		}
		Queue<Integer> queue = new LinkedList<>();
		for (int i = 0; i < mn; i++) {
			if (ins[find(i)] == 0 && !queue.contains(find(i))) {
				queue.add(find(i));
			}
		}
		int[] idx = new int[mn];
		int id = 1;
		while (!queue.isEmpty()) {
			int size = queue.size();
			while (size > 0) {
				int cur = queue.poll();
				idx[cur] = id;
				for (int nxt : nexts.get(cur)) {
					if (--ins[nxt] == 0) {
						queue.add(nxt);
					}
				}
				size--;
			}
			id++;
		}
		int[][] ans = new int[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				ans[i][j] = idx[find(i * n + j)];
			}
		}
		return ans;
	}

	private void union(int id1, int id2) {
		p[find(id2)] = find(id1);
	}

	private int find(int id) {
		if (p[id] != id) {
			p[id] = find(p[id]);
		}
		return p[id];
	}

	@Override
	public void debug4() {
		this.matrixRankTransform(H.str2array1("[[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
